package edu.cmu.cs211.snake.util;

import java.util.AbstractSet;
import java.util.NoSuchElementException;
import java.util.Iterator;

//The docs are mostly the same as the Java 5 documentation, which have
//been copied and pasted from the shared source version, under the
//JRL: http://java.net/jrl.csp

/**
 * This class implements the Set interface, backed by a hash table. It makes no
 * guarantees as to the iteration order of the set; in particular, it does not
 * guarantee that the order will remain constant over time. This class permits
 * the null element.
 * <p>
 * This class offers constant time performance for the basic operations (<tt>add</tt>,
 * <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>), assuming the
 * hash function disperses the elements properly among the buckets.
 * <p>
 * 
 * There are a few important requirements for your impl. of this data structure:
 * <ul>
 * <li>You <em>must</em> support constant time operations</li>
 * <li>You <em>may not</em> use any collection classes from <code>java.util.*</code></li>
 * <li>You <em>must</em> resize your hashtable according to the load factor</li>
 * </ul>
 */
public class MyHashSet <E> extends AbstractSet <E> {
	
	// fields
	/*
	 * the hashtable is implemented with an array of linked list: separate chaining
	 */
	private Node[] table;
	private int size;	// total number of elements in the table
	private float loadFactor;	// a float that decides when the table needs to be resized
	private int orginalSize;	// original table size when the constructor's called. used for clear
	private int primeTableSize = -1;	// index of the PRIME_TABLE array
	
	// a nice prime to start with (do not change this)
	private static final int DEFAULT_INITIAL_CAPACITY = 11;

	// a good load factor (do not change)
	private static final float DEFAULT_LOAD_FACTOR = 0.75f;

	// used to find a prime number when increasing table size
	private static final int [] PRIME_TABLE = {
		11,
		19,
		37,
		73,
		109,
		163,
		251,
		367,
		557,
		823,
		1237,
		1861,
		2777,
		4177,
		6247,
		9371,
		14057,
		21089,
		31627,
		47431,
		71143,
		106721,
		160073,
		240101,
		360163,
		540217,
		810343,
		1215497,
		1823231,
		2734867,
		4102283,
		6153409,
		9230113,
		13845163
		};

	/**
	 * Constructs a new, empty set; the backing table has default initial
	 * capacity (11) and load factor (0.75).
	 */
	public MyHashSet () {
		table = new Node[DEFAULT_INITIAL_CAPACITY];
		size = 0;
		this.orginalSize = DEFAULT_INITIAL_CAPACITY;
		loadFactor = DEFAULT_LOAD_FACTOR;
		this.primeTableSize = 0;
	}

	/**
	 * Constructs a new, empty set; the backing table has the specified initial
	 * capacity and default load factor, which is <tt>0.75</tt>.
	 * 
	 * @param initialCapacity
	 *            the initial capacity of the hash table.
	 * @throws IllegalArgumentException
	 *             if the initial capacity is less than zero.
	 */
	public MyHashSet (int initialCapacity)
	{	
		if(initialCapacity < 0 )
		{
			throw new IllegalArgumentException();
		}
		
		
		table = new Node[(initialCapacity == 0) ? DEFAULT_INITIAL_CAPACITY : initialCapacity];
		
		// update the PRIME_TABLE index according to user's initialCapacity
		for(int i = 0; i < PRIME_TABLE.length; i++)
		{
			if(initialCapacity < PRIME_TABLE[i])
			{
				this.primeTableSize = i;
			}
		}
		
		size = 0;
		loadFactor = DEFAULT_LOAD_FACTOR;
		this.orginalSize = initialCapacity;
	}

	/**
	 * Constructs a new, empty set; the table has the specified initial capacity
	 * and the specified load factor.
	 * 
	 * @param initialCapacity
	 *            the initial capacity of the hash map.
	 * @param loadFactor
	 *            the load factor of the hash map.
	 * @throws IllegalArgumentException
	 *             if the initial capacity is less than zero, or if the load
	 *             factor is nonpositive.
	 */
	public MyHashSet (int initialCapacity, float loadFactor)
	{
		if(initialCapacity < 0 || loadFactor <=0 )
		{
			throw new IllegalArgumentException();
		}
		
		// update the PRIME_TABLE index according to user's initialCapacity
		for(int i = 0; i < PRIME_TABLE.length; i++)
		{
			if(initialCapacity < PRIME_TABLE[i])
			{
				this.primeTableSize = i;
			}
		}
		
		table = new Node[(initialCapacity == 0) ? DEFAULT_INITIAL_CAPACITY : initialCapacity];
		size = 0;
		this.loadFactor = loadFactor;
		this.orginalSize = initialCapacity;
	}

	/**
	 * Returns the number of elements in this set (its cardinality).
	 * 
	 * @return the number of elements in this set (its cardinality).
	 */
	@Override
	public int size ()
	{
		return size;
	}

	/**
	 * Returns <tt>true</tt> if this set contains the specified element.
	 * 
	 * @param o
	 *            element whose presence in this set is to be tested.
	 * @return <tt>true</tt> if this set contains the specified element.
	 */
	@Override
	public boolean contains (Object o)
	{
		if(size == 0)	// table is empty
			return false;
		int hash = (o == null)? 0 : o.hashCode();	
		int key = Math.abs(hash % this.table.length);	// retrieve the hashcode of o
		
		// walk down the linked list and look for o
		if(table[key] != null)
		{
			Node head = table[key];
			while(head != null)
			{
				if(head.o == null)//handle null elements
					return true;
				if(head.o.equals(o)) // found 
					return true; 
				head = head.next;
			} 
		}
		return false; // not found
	}
	
	/**
	 * Adds the specified element to this set if it is not already present.
	 * 
	 * @param e
	 *            element to be added to this set.
	 * @return <tt>true</tt> if the set did not already contain the specified
	 *         element.
	 */
	@Override
	public boolean add (E e)
	{	
		int hash = (e== null)? 0 : e.hashCode();	// handle null: if e == null, insert into bucket 0		
		int key = Math.abs(hash % this.table.length);
		Node head;
		
		if(table[key] != null)
		{
			head = table[key];
			while(head != null)
			{
				if(head.o == null)
					return false;
				if(head.o.equals(e)) // found 
					return false; 
				head = head.next;
			} 
		}
		
		if((head = table[key]) != null)//exists
		{
			Node n = new Node();
			n.o = e;
			n.next = head; // insert to head of the linked list
			table[key] = n; // set n to head
			size++;
			return true;
		}
		else
		{
			//resize if it does not exist..
			if(((float)(size + 1)/(float)table.length) > this.loadFactor)
			{
				resize();
				System.out.println("RESIZE");
				key = Math.abs(hash % this.table.length);
			}
			Node n = new Node();
			n.o = e;
			table[key] = n; 
			size++;
			return true;
		}
	}
	
	/*
	 * insertIntoNewTable: insert object o into nTable and return nTable
	 */
	private Node[] insertIntoNewTable(Object o, Node[] nTable, int hash)
	{
		Node head;
		int key = Math.abs(hash % nTable.length);
		
		if((head = nTable[key]) != null)//exists: link to the correct bucket
		{
			Node n = new Node();
			n.o = o;
			n.next = head;
			nTable[key] = n;
			return nTable;
		}
		else	// doesn't exist: put in a new bucket
		{
			Node n = new Node();
			n.o = o;
			nTable[key] = n; 
			return nTable;
		}
	}
	
	/*
	 * resize: resize the current hashtable and REHASH all elements into the new table
	 * then redirect the reference of the current table to the new table
	 */
	private void resize()
	{
		if (size == Integer.MAX_VALUE)	// size cannot get any bigger, simply return
			return;
		
		// new table
		Node [] newTable = new Node[(this.primeTableSize > 0 && this.primeTableSize +1 < PRIME_TABLE.length) ? ++this.primeTableSize : this.table.length * 2];
		
		//resize table
		for(int i = 0; i < table.length; i++)
		{
			if(table[i] != null)
			{
				Node head = table[i];
				while(head != null)
				{
					int h = (head == null) ? 0 : head.o.hashCode();
					newTable = insertIntoNewTable(head.o,newTable,h);
					//insert into new table.
					head = head.next;
				}
			}
		}
		this.table = newTable;	//redirect the reference to table to newTable
	}

	/**
	 * Removes the specified element from this set if it is present.
	 * 
	 * @param o
	 *            object to be removed from this set, if present.
	 * @return <tt>true</tt> if the set contained the specified element.
	 */
	@Override
	public boolean remove (Object o)
	{
		
			int hash = (o== null)? 0 : o.hashCode();	// handle null	
			int key = Math.abs(hash % this.table.length);
			if(table[key] != null)
			{
				Node head = table[key];
				Node prev = null;
				while(head != null)
				{
					if(head.o.equals(o))
					{
						if(table[key] == head) //if head is the first one..
							table[key] = head.next;
						else //not the first one..
							prev.next = head.next;
						size --;
						return true;
					}
					prev = head;
					head = head.next;
				}
			}
			return false;
		}

	/**
	 * Removes all of the elements from this set.
	 */
	@Override
	public void clear ()
	{
		size = 0;
		loadFactor = DEFAULT_LOAD_FACTOR;
		this.table = new Node [this.orginalSize];
	}
	
	/**
	 * Returns an iterator over the elements in this set. The elements are
	 * returned in no particular order. You do <em>not</em> have to implement
	 * fail-fast behavior (ie, ConcurrentModificationException) or remove.
	 * 
	 * @return an Iterator over the elements in this set.
	 */
	public Iterator <E> iterator ()
	{
		return new Iterator<E>(){
			private int itrBucket = 0;	//current iterator bucket
			private Node itrNode = null;	// current iterator node
			private int traversed = 0;	// number of node traversed: used for hasNext function
			
			@Override
			public boolean hasNext() 
			{
				return traversed < size;
			}

			@Override
			public E next() 
			{
				//skip over null's
				while(itrBucket < table.length && table[itrBucket] == null)
				{
					itrBucket++;//out of bounds..
				}
				
				if(itrBucket >= table.length)
					throw new NoSuchElementException();
				
				//get node from the new bucket.
				if(itrNode == null)
					itrNode = table[itrBucket]; 
				
				//if the next node is null, we are are the end of the chain
				if(itrNode.next == null)
				{
					E o = (E)itrNode.o;
					itrNode = null;
					itrBucket++;
					traversed++;
					return (E)o;
				}
				//if next node is not null, dont change bucket, keep going..
				else if (itrNode.next != null)
				{
					E o = (E)itrNode.o;
					itrNode = itrNode.next;
					traversed++;
					return (E)o;
				}
				throw new NoSuchElementException();
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}
}
